I. Field of the Invention
The invention relates to communication systems. More particularly, the invention relates to a communication system using convolutional decoding.
II. Description of the Related Art
In modern day communication systems, the channel provided to connect two communications units can introduce a significant number of errors into the data which is passed over the channel. For example, a wireless channel is especially prone to introduce errors. Errors may occur from extraneous signal energy on the channel such as energy introduced by thermal noise, other users of the same system, and other systems operating within the same geographic region. In addition, especially in a terrestrial wireless channel, the channel is subject to multipath fading effects which may cause a signal to interfere with itself.
Modern encoding techniques have been developed in order to promote the successful transfer of data over an imperfect channel. These techniques allow a receiving unit to detect and correct for errors introduced during the transmission process.
FIG. 1 is a block diagram showing a conventional transmitting unit 2 and a receiving conventional unit 18 using a convolutional encoding and a data puncturing scheme. A convolutional encoder 4 encodes the incoming information bit stream. The convolutional encoder 4 responds to the information bit steam and creates a symbol stream by the introduction of redundancy and symbol interdependence so that error correction may be performed at the receiving unit 18.
A typical convolutional encoder 4 is comprised of a series of shift registers such as shift registers 6A-6D. As each information bit is received, each of the shift registers 6A-6C transfers its content to the next successive shift register 6B-6D and receives a new input bit directly from the information bit stream or the preceding shift register. The content of shift register 6D is discarded when the next information bit is received.
The output of selected ones of shift registers 6A-6D are connected to adders 8A and 8B such that each of the adders 8A and 8B produces one symbol digit for each information bit that is received. Note that not all of the shift registers 6A-6D are connected to each of the adders 8A and 8B and that the shift registers which are connected to the adder 8A are different from those connected to the adder 8B such that the output sequence from the adder 8A is different from the output sequence from the adder 8B. Thus, each time that a new information bit is shifted into the convolutional encoder 4, the convolutional encoder 4 produces two distinct symbols. For this reason, the convolutional encoder 4 is said to produce rate one-half (R=1/2) encoded symbols.
As each bit shifts into the convolutional encoder 4, its value contributes to determining the value of the symbols output by the adders 8A and 8B for five information bit increments. For this reason, the particular convolutional encoder 4 is said to have a constraint length equal to five (K=5). In this way, redundancy and symbol interdependence is introduced through the encoding process. Due to the redundancy and symbol interdependency introduced by the convolutional encoder 4, an error-free information bit stream may be decoded at the receiving unit even if a portion of the symbols are missing or corrupted.
In addition to the symbol data which is lost or corrupted as it is passed over the error-prone channel, the transmitting unit may purposefully delete or overwrite a portion of the symbol data. For instance, when constrained by a given communication system, convolutional encoding may result in more bits than can be transmitted within the constraints of the system. Accordingly, bits are often deleted after convolutional encoding. The deletion of the bit is often known as "puncturing." For the deletion of bits, the bits are typically punctured in accordance with a known pattern such as one of every n bits. Accordingly, the decoder is able to determine which bits have been punctured at the receiving end because the puncturing occurs according to a predetermined pattern. In conventional systems, the receiver, such as the receiver 18 includes depuncture logic which is configured with the pattern and fills the punctured bits (i.e., inserts bits to fill in for the punctured bits) with zeros. The depuncture logic does not typically fill with a logic "zero," but in a system where logical "1" is represented by a negative one and logical "0" is represented by a positive one, the depuncture logic fills in a value of zero, that being the value halfway between one and negative one. The receiving unit then provides a simple convolutional decoding operation 24 using the filled bits in place of the punctured bits which were removed at the transmitting end.
The transmitting unit 2 of FIG. 1 uses a data puncturing scheme. The output of the convolutional encoder 4 is passed to puncture logic 10. The puncture logic 10 punctures the symbol data removing bits according to a known pattern. The number of bits is thereby decreased, and passed to the modulator 12. The modulator 12 modulates the data. And the modulated symbol stream is transmitted over the communication channel. At the receiving unit 18, a demodulator 20 may create soft decision data. Soft decision data essentially reflects the probability that the symbol data was properly received. For example, if the incoming stream of data is assumed to be a stream of 1's and -1's, the demodulator 20 may produce data quantized into a number of discrete values between 1 and -1. If the signal energy for a particular bit is high, the demodulator 20 produces an absolute symbol value close to 1. As the symbol energy decreases, the demodulator 20 produces symbol values which approach zero. The soft decision data is passed to the depuncture logic 22. The depunctured logic fills in the punctured bits according to the known pattern with erasures. Erasures are zeros which reflect neither a one nor a negative one. The depuncture logic 22 then passes the resulting data stream to the convolutional decoder 24.
Due to the redundancy introduced by the convolutional encoder 4, error-free data may be recovered from the punctured symbol stream by the convolutional decoder 24. Standard convolutional decoders make use of the additional information available in soft decision data to recover the transmitted sequence with an even higher reliability than achieved with "hard decision" values. (Hard decision values result if each incoming symbol data is mapped into either a 1, a -1 or a 0 rather than a plurality of non-unity, non-zero values as well.) Additional information concerning soft-decision decoding may be found in the second edition of "Digital Communications" by John G. Proakis, published by McGraw-Hill in 1989. Additional information of convolutional decoding in general may be found in the book entitled "Trellis Decoding of Block Codes: A Practical Approach" by Bahram Honary and Gerik Markarian published by Kluwer Academic Publishers in 1997.
The convolutional decoder 24 produces a maximum likelihood decoded information bit stream which is passed to a processing unit 26. The processing unit 26 may use a variety of means well-known in the art to determine whether the decoded information bit stream accurately reflects the transmitted information bit stream. For example, the incoming information bit stream may comprise a cyclic redundancy check (CRC) sequence which can be used to detect errors at the receiving unit 18. In the case of voice data, erroneously received information bits may be discarded before the bit stream is passed to a voice decoder. In the case of digital data transfer, the erroneously received information bits may be retransmitted by the transmitting unit.
Alternatively, as shown in FIG. 2, rather than delete the bits from the convolutional encoded data stream, a multiplexer 11 replaces some of the bits with supplemental information bits. This still results in bits being punctured from the primary data stream, but the punctured bits are replaced with additional bits. Other than the multiplexer 11, the transmitting unit 3 is the same as the transmitting unit 2 of FIG. 1. Accordingly, in this embodiment, the actual number of bits transmitted is not reduced. However, the number of bits from a particular convolutionally encoded bit stream is reduced. The resulting bit stream is passed to the modulator 12 which is then transmitted over the communication channel as described above. Similarly, as described above, the demodulator 20 receives the transmitted data which is then provided to a demultiplexer 23. The demultiplexer 23 divides the supplemental information bits from the primary symbol stream and replaces the missing symbols with erasures as described above. The resulting symbol stream is provided to the convolution decoder 24 as described above.
The supplemental information may be control information which is used to govern the link. For example, the supplemental information may be power control information, handover information, or paging information. The supplemental information replaces the symbol data in this way creating a subchannel which piggybacks onto the main information channel. Due to the redundancy and symbol interdependency introduced by the convolutional encoder 3, an error-free information bit stream may be decoded even though a portion of the symbols have been replaced with the punctured data.
The deficiency of the prior art is seen when the combined effect of the punctured data scheme and the channel characteristics increases the error rate beyond an acceptable limit. In a voice system, if the error rate becomes excessive, the decoded voice output becomes difficult to comprehend. In the case of digital data transfer, an increase in error rate can greatly reduce the effective data rate of the system if system resources are continually consumed by the repetition of erroneously received data.